#include <bits/stdc++.h>
using namespace std;
int partition(vector<int>&a,int begin,int end,int length)
{
    int index = rand()%(end-begin)+begin;
    int small = begin-1;
    swap(a[index],a[end]);
    for(int index = begin;index<end;index++)
    {
        if(a[index]<a[end])
        {
            small++;
            if(small != index)
                swap(a[index],a[small]);
        }
    }
    small++;
    swap(a[small],a[end]);
    return small;
}
void quicksort(vector<int>&a,int begin,int end,int length)
{
    if(begin == end)
        return;
    int privot = partition(a,begin,end,length);
    if(privot>begin)
        quicksort(a,begin,privot-1,length);
    if(privot<end)
        quicksort(a,privot+1,end,length);
}
int main() {
    vector<int> a = {4,3,8,2,6,5};
//    partition(a,0,5,3);
    quicksort(a,0,5,3);
    for(auto i:a)
        cout<<i<<" ";
    return 0;
}
